package com.springboot.prac.prac_leecode.lee02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

/**
 * @author : syl
 * @date : 2022/9/6 9:34
 * @desc : 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 * 思路1：将两个listNode数值取出，拼接成数值，两者相加之后的结果，放入链表(由于要求是每个节点数量是0-100位，位数较多时，该思路不适用)
 * 思路2：将链表转为数组，然后将结果数组放入链表
 * 题目链接：https://leetcode.cn/problems/add-two-numbers/
 */
public class LeeCode_02 {

    public static void main(String[] args) {
        Integer[] initArray01 = {1, 2, 9, 8, 9, 5, 6, 4, 3, 3, 4, 5, 9, 1, 2, 9, 8, 9, 5, 6, 4, 3, 3, 4, 5, 9, 1, 2, 9, 8, 9, 5, 6, 4, 3, 3, 4, 5, 9, 1, 2, 9, 8, 9, 5, 6, 4, 3, 3, 4, 5, 9, 1, 2, 9, 8, 9, 5, 6, 4, 3, 3, 4, 5, 9, 1, 2, 9, 8, 9, 5, 6, 4, 3, 3, 4, 5, 9, 1, 2, 9, 8, 9, 5, 6, 4, 3, 3, 4, 5, 9};
        Integer[] initArray02 = {4, 5, 6, 7, 0, 8, 1, 2, 9, 8, 9, 5, 6, 4, 3, 3, 4, 5, 9, 1, 2, 9, 8, 9, 5, 6, 4, 3, 3, 4, 5, 9, 1, 2, 9, 8, 9, 5, 6, 4, 3, 3, 4, 5, 9, 1, 2, 9, 8, 9, 5, 6, 4, 3, 3, 4, 5, 9, 1, 2, 9, 8, 9, 5, 6, 4, 3, 3, 4, 5, 9};
        ListNode listNode01 = transferArrayToNode(initArray01);
        ListNode listNode02 = transferArrayToNode(initArray02);
        Integer[] array01 = transferNodeToArray(listNode01);
        Integer[] array02 = transferNodeToArray(listNode02);

        // 数组相加
        long start = System.currentTimeMillis();
        // 自己的解法
        // Integer[] result = sum(array01, array02);
        // 网上解法
        ListNode listNode = addTwoNumbers(listNode01, listNode02);
        long end = System.currentTimeMillis();
        System.out.println(end - start + "ms");

        Integer[] array = transferNodeToArray(listNode);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 链表转数组
     *
     * @param node
     * @return
     */
    public static Integer[] transferNodeToArray(ListNode node) {
        List<Integer> list = new ArrayList();
        list.add(node.getData());
        ListNode next = node.getNext();
        while (Objects.nonNull(next)) {
            System.out.println("当前遍历数值：" + next.getData());
            list.add(next.getData());
            next = next.getNext();
        }
        return list.toArray(new Integer[list.size()]);
    }

    /**
     * 数组转链表
     *
     * @param array
     * @return
     */
    public static ListNode transferArrayToNode(Integer[] array) {
        ListNode finalNode = null;
        ListNode lastNode = null;
        for (Integer data : array) {
            if (Objects.isNull(finalNode)) {
                finalNode = new ListNode(data);
                lastNode = finalNode;
            } else {
                lastNode.setNext(new ListNode(data));
                lastNode = lastNode.getNext();
            }
        }
        return finalNode;
    }

    private static Integer[] sum(Integer[] array01, Integer[] array02) {
        Integer[] longerArray = array01.length >= array02.length ? array01 : array02;
        Integer[] shorterArray = array01.length <= array02.length ? array01 : array02;
        System.out.println("longerArray: " + Arrays.toString(longerArray));
        System.out.println("shorterArray: " + Arrays.toString(shorterArray));
        List<Integer> list = new ArrayList();
        Boolean flag = false;
        for (int i = 0; i < longerArray.length; i++) {
            Integer sum = null;
            if (i + 1 <= shorterArray.length) {
                sum = longerArray[i] + shorterArray[i];
            } else {
                sum = longerArray[i];
            }

            if (flag) {
                sum = sum + 1;
            }

            // 两数之和超过10，进位1
            if (sum > 9) {
                flag = true;
                sum = sum - 10;
            } else {
                flag = false;
            }

            list.add(sum);
        }
        return list.toArray(list.toArray(new Integer[list.size()]));
    }

    // 借鉴网上解法-该解法简洁明了
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0);
        ListNode cursor = root;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int l1Val = l1 != null ? l1.getData() : 0;
            int l2Val = l2 != null ? l2.getData() : 0;
            int sumVal = l1Val + l2Val + carry;
            carry = sumVal / 10;

            ListNode sumNode = new ListNode(sumVal % 10);
            cursor.setNext(sumNode);
            cursor = sumNode;

            if (l1 != null) l1 = l1.getNext();
            if (l2 != null) l2 = l2.getNext();
        }

        return root.getNext();
    }
}
